package exam.demo19;

import java.util.Scanner;

public class Test2 {
    static int m = 0, n = 0;
    public static int maxValue (int[][] grid) {
        // write code here
        Scanner scanner = new Scanner(System.in);
        m = grid.length;
        n = grid[0].length;
        int[][] prices = new int[m + 2][n + 2];
        com(grid, 1, 1, prices);

        return prices[m][n];
    }

    public static void com(int[][] grid, int i, int j, int[][] prices) {
        if(i > m || j > n) {
            return;
        }
        prices[i][j] = Math.max(prices[i-1][j], prices[i][j-1]) + grid[i-1][j-1];
        com(grid, i, j+1, prices);
        com(grid, i+1, j, prices);
    }

    // [[1,3,1],[1,5,1],[4,2,1]]
    // {1, 3, 1}, {1, 5, 1}, {4, 2, 1}, {3, 4, 8}
    public static void main(String[] args) {
        int[][] grid = {{3, 2}, {4, 1}};
        System.out.println(maxValue(grid));
    }
}
